package com.example.algorithm.sort;

// 学习顺序：第五
// 冒泡排序的进化版，第一个数据把做全量对比，把比这个数小的放到它左边，大的放到右边，然后分别对左右两部分再进行快排，递归计算完成排序。
// 也是分治法的使用，与归并某种意义上相反：归并是不断分成两份然后合并，快排是不断分成两个部分排序，快排一般会比归并快3倍，并且可以通过随机化快速排序规避最差情况(n^2 )，保证nlgn复杂度。
// 复杂度：n^2，但是平均情况很快，达到nlgn
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {5, 3, 9, 8, 4, 2, 6, 1, 7};

        System.out.println("排序前的数组：");
        printArray(array);

        quickSort(array, 0, array.length - 1); // 左右指针的初始位置在数组的头部和尾部。

        System.out.println("\n排序后的数组：");
        printArray(array);
    }

    // 快速排序方法
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) { // low、high分别是左右指针的初始位置。

            // pivotIndex就是选取的那个区分大小两边的值的所在的位置，也就是索引。pivot是中心、枢的意思。这里应该是中心索引的意思。
            int pivotIndex = partition(array, low, high); // 找到基准元素的位置

            quickSort(array, low, pivotIndex - 1); // low此时还是0，pivotIndex - 1基准元素左边的那个数组。基准元素自己本身的位置不用动了，后续它也不参加任何排序。
            quickSort(array, pivotIndex + 1, high); // pivotIndex + 1是基准元素右边的元素。high还是原先的array.length - 1
        }
    }

    // 划分方法
    public static int partition(int[] array, int low, int high) {
        int pivot = array[low]; // 选择第一个元素作为基准元素。快速排序默认都是这么选的。
        int i = low, j = high;

        while (i < j) { // i是左指针，j是右指针。当它们没有重合的时候，while一直执行。

            // 从右向左找到第一个小于基准元素的元素。
            // array[j] >= pivot这句会最先不满足，然后这个while就结束了。
            while (i < j && array[j] >= pivot) { // array[j] >= pivot是我们所期待的那样，如果满足，那其实不需要做什么，直接向左移动右指针就行。
                j--; // 像左移动右指针。
            }

            // 下面就是把array[j]赋值给array[i]，将小于基准元素的元素放到左指针目前的位置。
            // 为什么array[j]恰恰要赋值给array[i]呢？因为i的左边是它已经检查过的，是确定是小于基准元素的。
            // 为什么赋值完之后要i++呢？想想如果不i++会怎么样。那么，下次让i向右移动的时候，是从array[j]这个值开始的。而这个已经确定小于基准元素。所以，这次比较是不必要的。所以要i++略过这个元素。
            if (i < j) {
                array[i++] = array[j];
            }

            // 下面这两段代码，与上面的我们可以总结为是镜像关系。上面的理解和记得，下面的必然理解和记得。
            while (i < j && array[i] <= pivot) {
                i++; // 向右移动左指针。
            }
            // 将大于基准元素的元素放到右边
            if (i < j) {
                array[j--] = array[i]; // 把左指针位置上的元素，赋值给右指针位置上的元素。
            }
        }

        // 当最外层的while不能走了之后，说明，已经重叠了。那么，此时的i的位置，就是放基准值的地方。
        // 回顾一下。我们先动j，然后动i。
        // (1)j动了一波之后，直接一直j--到j == i。那此时基准值放置时确定位置用j还是用i都是一样的。
        // (2)j动了一波之后，没与重合。然后i再动一波，运动到i = j了，同理，那还不是用哪个确定位置都是一样的吗。
        // (3)j动了一波，没有重合。然后i再动一波，还是没有重合。然后j再动一波，一直动到重合了。那还是用j还是用i都是一样的。
        // 将基准元素放到最终位置
        array[i] = pivot;
        return i;
    }

    // 打印数组方法
    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}


// 后记：
// 问：将基准元素放到最终位置，array[i] = pivot;return i;这段代码中的i如果用j是不是一样的。因为i和j最后必然在某个时刻是会值一样嘛？
// chatGPT:
// 在快速排序的实现中，选择基准元素后，通过 partition 方法将数组分割成两部分。在分割过程中，i 和 j 分别是左右两个指针，分别从数组的两端向中间移动，直到它们相遇。
// 在这段代码中，`array[i] = pivot;` 将基准元素放到最终位置，其中 i 是左指针最后所在的位置，也是基准元素应该插入的位置。
// 如果使用 j 来代替 i，最终结果也是一样的，因为在最后一次交换后，i 和 j 的值是相同的(这个我用本程序实际试验过了，用i还是用j最后获取到的结果确实是一样的)。
// 但是，使用 i 更加直观，因为在整个快速排序过程中，i 代表的是左指针的位置，与快速排序算法的思想更加契合。

// 关于左右两个指针，它们不是互换元素，是一个替换掉另一个指针位置上的元素这件事
// 这个听起来有点反直觉，你可能会觉得，当一个替换掉另一个，比如，右先动，然后右边的替换掉左边指针位置上的值，那么，右边指针那个位置的
// 值在数列里面那不会有两份。但是，其实，接下来左边动的时候，左边指针所在位置上的值，会替换掉右边指针上那个位置上的值，现在，就是左边那个位置上的值有两份了。
// 不管怎么样，数列里面，只会有一个指针所在的位置对应的值有重复一次。但是，最后当左右指针重合的时候，左右指针重合的那个位置上，肯定也是一个指针所在位置的重复值。
// 但是呢，最后，我们会用基准值替换掉左右指针所在位置的那个重复值。这样下来，最后，整个数组就没有重复值了。
// 这个问题，在 关于排序算法的一些个人备注笔记-P 这篇印象笔记里面已经画图演示的很清楚了。一定要移步到那里。

// 关于归并排序和快排的一些总结。
// 由于归并和快排都是属于某种分而治之的方法，所以我把它们放在一起，作为一类来说。
// 但是，事实上，它们的区别是非常大的。归并的话，是固定按照数组的长度来大致分分为两份，然后一直递归这样分下去，分到每组只有两个元素的时候排序，排好在递归式地从小往大返回过程，合并两个有序的数组。其实，它是需要额外的空间的。
// 而快熟排序，不是用长度来划分。是按照数组里面元素的值的大小来划分的。它是先在某个递归层级确定一个基准值，然后借助双指针的一套规则，把数组反正分为两边，左边都是小值，右边都是大值。这个过程是递归的，一直这样分到没法再继续分。然后此时，这个数组就自然就是有序的。和规并不太一样吧，它不需要还有个合并有序数组的过程。因为，它是在原数组上做一系列的交换操作，是直接在原数组上操作的。
